#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <ctype.h>

using namespace std;


char opt_set[10] = "+-*/()";

bool is_operator(char sg)
{
	for (int i = 0; i < 7; i++)
	{
		if (sg == opt_set[i])
			return true;
	}
	return false;
}

string del_unnecessary(string& thestring) //delete the unnecessary string except for bumbers,operators and dot.
{
	string s;
	//cout << thestring.length() << endl;

	for (int i = 0; i < thestring.length(); i++)
	{
		if (isdigit(thestring[i]) || is_operator(thestring[i]) || thestring[i] == '.')
		{
            s += thestring[i];
		}
	}
    return s;
}

bool is_legal(string& str) //determind whether the expression is legal.
{
	for (int i = 0; i < str.length(); i++)//the operator '+' and '-' cannot be the last term
	{
		if (str[i] == '+' || str[i] == '-') 
		{
			if (i = str.length()-1)
				return false;
		}
	}

	if(str[0]=='*' || str[0]=='/' || str[str.length()-1]=='*' || str[str.length() - 1] == '/')//the operator '*' and '/' cannot be the first and last term
	{
	return false;
    }
	
	int dot_num = 0;
	for (int i = 0; i < str.length(); i++)//the number of dot cannot more than 1
	{
		if (str[i] == '.')
			dot_num += 1;
		if (dot_num > 1) 
		{ return false; }
	}

	int brac = 0;
	for (int i = 0; i < str.length(); i++)//the bracket must be in pair
	{
		if (str[i] == '(')
		{
			brac += 1;
		}
		if (str[i] == ')')
		{
			brac -= 1;
		}
		if (brac > 0 || brac < 0 )
		{
			return false;
		}
	}

	return true;
}

int priority(char opt)//the priority of the operators.
{
	int p = -2;
	if (int(opt) >= 48 && int(opt) <= 57)
		p = -1;
	else if (opt == '+' || opt == '-')
		p = 1;
	else if (opt == '*' || opt == '/')
		p = 2;
	else if (opt == '(' || opt == ')')
		p = 3;

	return p;
}
	
stack<char> operators;//store operators.
stack<double> value;//store value.

void eval()
{
	double b = value.top();
	value.pop();
	double a = value.top();
	value.pop();
	char c = operators.top();
	operators.pop();
	double r;
	if (c == '+')
	{
		r = a + b;
	}
	else if (c == '-')
	{
		r = a - b;
	}
	else if (c == '*')
	{
		r = a * b;
	}
	else if (c == '/')
	{
		r = a / b;
	}
	value.push(r);
}

void calculator(string& thestring)
{
	thestring = '0' + thestring;//if the first term is '-' or '+'.
	for (int i = 0; i < thestring.length(); i++)
	{
		char s = thestring[i];
		if (isdigit(s) || s == '.')
		{
			string x; int j = i;
			while (j < thestring.length() && isdigit(thestring[j]))
			{
				x += j;
				j += 1;
			}
			value.push(atof(x.c_str()));
			i = j - 1;	
		}
		else if (is_operator(s)) 
		{
			while (operators.size() && priority(operators.top()) >= priority(s) )
			{
				eval();
			}
			operators.push(s);
		}
	}
}

void show_queue(queue<double> sg)
{
	queue<double> ss = sg;
	while (!ss.empty())
	{
		cout << '\t' << ss.front();
		ss.pop();
	}
	cout << '\n';
}

void show_stack(stack<double> sg)
{
	stack<double> ss = sg;
	while (!ss.empty())
	{
		cout << '\t' << ss.top();
		ss.pop();
	}
	cout << '\n';
}

int main()
{
	
	string a;
	cout << "Plese enter the Mathematical expression:" << endl;
	cin >> a;
	//cout << a << endl;
	cout << del_unnecessary(a) << endl;
	int s=is_legal(a);
	if (s == 0)
	{
		cout << "The Mathematical expression is illegal." << endl;
	}
	else 
	{ cout << "The Mathematical expression is legal." << endl;}
	return 0;
	
	//show_stack(value);


	//cout << value << endl;

	//int num = a.length();
	/*for (int i = 0; i < a.length(); i++)
	{
		cout << a[i] << endl;
	};*/
	

	//queue<double> s;
	//s.push(10.1);
	//s.push(a);
	//show_queue(s);

}